This invention relates generally to techniques for detecting and correcting errors on storage media, and more particularly, to techniques for detecting and correcting errors in encoded data, especially data to be stored in memory such as a DRAM.
Conventional methods for DRAM protection involve the use of Hamming codes. The check bits in a Hamming code are parity bits for the data bits. Each check bit provides the parity for a unique subset of the data bits. If an error occurs (i.e., one or more bits change state), one or more syndrome bits will be asserted. Which syndrome bits are asserted may also be used to determine which data bit changes state, and enable the correction of the error.
One common use of Hamming codes is to correct single bit errors within a group of data. A single error correcting Hamming code is able to correct a single error. The error detection capability of the code may be increased by adding an additional check bit. The use of an additional check bit allows the Hamming code to detect double bit errors and correct single bit errors. The addition of a bit to increase the data detection capabilities of a Hamming code is referred to as an extended Hamming code.
The Hamming distance is the number of bits that disagree between two binary sequences of the same length. For example, if a codeword x consists of ‘10000’ and a codeword y consists of ‘01100,’ the Hamming distance is equal to 3. In conventional methods, in order to detect n bit errors, a coding scheme requires the use of codewords with a Hamming distance of at least n+1. In addition, a coding scheme with at least a Hamming distance of 2n+1 between the codewords is required.
The distance d of a code is defined as the minimum Hamming distance between all pairs of codewords in the code. Codes with a larger value of d have a greater error-correcting capability. Codes with parameters N and k are referred to as (N, k) codes. If the distance d is also known, then the codes are referred to as (N, k, d) codes.